1. Field of Invention
The present invention generally relates to programming interfaces between application programs and physical devices in a computer system.
2. Description of Prior Art
A process, which exists in a current or suspended state of execution, consists of a sequence of microprocessor instructions that have been loaded into random access memory in order to perform a task together with some private memory. The private memory is utilized to record state information during periods of suspended activity and as a buffer to store input and output data. Multiple processes which are simultaneously present in a computer system are known in the prior are as concurrent processes. Concurrent processes compete for limited system resources such as cache memory, random access memory, microprocessor instruction cycles, and access to physical devices. A mutual exclusion constraint exists in that two or more processes are not able to access the same system resource at the same instant of time. Cost-effective, personal computer systems, for example, provide only a single microprocessor for the execution of concurrent processes, in which case only one process is in a current state of execution and all others are in a suspended state of execution.
An application program provides a mechanism by which the human operator instructs the computer to perform tasks. The application spawns either a single process or multiple processes that are linked by cooperative relationships. Furthermore, multiple applications may be present in a computer system. An operating system is a set of functions that provide, at a minimum, a means of invoking application programs for execution and a man-machine interface between the human operator and computer system when no application programs are present. Operating systems also provide services that are common to a variety of applications and which require utilization of physical devices. Scheduling services, for example, requires utilization of a timing device to manage concurrent process access to microprocessor instruction cycles. A graphical user interface provides access to the video graphics adapter and mouse. In another example, dynamic memory management provides access to random access memory. Other system services that may or may not be provided by a particular operating system include inter-process communication, network connectivity, web browsing, dynamic-link library support, virtual memory management, cache management, security from external tampering, and protection from computer viruses. Operating systems are distinguished by the number and functionality of system services that they provide, the resources that are consumed in order to provide these services, and the intellectual complexity of the application program interface.
Certain operating system services that are explicitly requested by application programs using an application program interface. Application program interfaces consist of data and a library of routines which are provided in a dynamic-linked library. The library of routines that are utilized by a specific application program are dynamically linked to that application program each time it is invoked by the operating system, and differ from routines in software libraries that are statically linked to the application program exactly one time prior to program execution. It is well known in the prior art that a maximum of one copy of the data and library of routines provided by a dynamic-link library is stored in random access memory at any given time, independently of the number of application programs which are present.
Referring to FIG. 1, a prior art programming interface between application programs and physical devices being utilized is shown. An operating system 10, two separate applications programs 41, 42 and three separate physical devices 1, 2, 3 are present. Next, the operating system consists of a kernel 20, three separate device drivers 11, 12, 13 and three separate application program interfaces 31, 32, 33.
The kernel 20 schedules the execution times of concurrent processes which are spawned by the application programs, application program interfaces, and device drivers. The kernel is itself a process and therefore must schedule its own activity. Microprocessor instruction cycles are viewed as a system resource, so that process execution time coincides with the scheduled allocation of microprocessor instruction cycles to that process. In some cases, concurrent processes operate independently of each other. In other cases, concurrent processes are linked by cooperative towards the goal of achieving some high level task. The cooperative relationships may be viewed as a sequence of cause-and-effect relationships. Furthermore, each cause-and-effect relationship involves a secondary process and one or more primary processes. The secondary process accepts as an input data and control information produced by the primary processes in order to perform an intermediate task towards the ultimate goal of completing some higher level task. A precedence constraint exists in that the availability of the data and control information produced by the primary processes must precede execution of the secondary process. The time elapsed time beginning when the secondary process is invoked to complete the task and ending with task completion equals the sum of the execution time and scheduling delay. The execution time equals the elapsed time beginning when the secondary process obtains the system resources and inputs which are necessary for task completion, and ending when the secondary process completes the task. The scheduling delay equals the elapsed time beginning when the secondary process is invoked to complete the task, and ending when the secondary process obtains the system resources and the inputs which are required for task completion.
Application programs 41, 42 utilize the application program interfaces 31, 32, 33 in order to request services that require utilization of the physical devices 1, 2, 3. In the prior art, application program interfaces 31, 32, 33 do not directly manipulate any of the physical devices 1, 2, 3. Instead, the application program interfaces incorporate a hardware-independent, abstract representation of generic physical devices. This representation is utilized to generate a sequence of abstract operations which are performed by the generic device in response to requests for services that require utilization of the physical devices. Abstract device operations generated by the application program interfaces, which vary in number depending upon the particular service that is requested by the application programs, are sent to the kernel in the form of variable-length messages. As an intermediate step in the processing, the application program interface executes any computational algorithms that are required to decompose requested services into the appropriate sequence of abstract device operations.
The kernel 20 accepts as an input messages containing a variable-length sequence of abstract device operations from the application program interfaces. Each abstract device operation is validated by the kernel in the case of operating systems that are alleged in the prior art to insure computer system integrity and to protect the system from external tampering. Next, the appropriate device driver is identified by the kernel and designated to manipulate the physical device as specified by the abstract device operations.
Device drivers provide a low-level interface to physical devices. Each device driver translates abstract device operations into actual device operations which are hardware-dependent and specific to the particular physical device in use. It can be seen by those skilled in the prior art that the application programs, application program interfaces, and kernel are independent upon the type of physical device being utilized. Hardware independence of the operating system is achieved by dynamically linking the kernel 20 with the set of device drivers 11, 12, 13 that are compatible with the particular set of physical devices 1, 2, 3, respectively, that are present.
Interrupts originating from the physical devices 1, 2, 3 are not delivered directly to application programs 41, 42. Instead, the device drivers 11, 12, 13 incorporate interrupt service routines which intercept and process interrupts originating from physical devices 1, 2, 3, respectively. The interrupt service routines send a message to the kernel 20 in order to communicate the results of intercepting and processing the interrupts. The kernel 20 dispatches these messages to the appropriate application program interfaces 31, 32, 33. Application program interfaces 31, 32, 33 perform additional processing on messages originating from device driver interrupt service routines, and output new messages to application programs 41, 42 indicating the results of the processing.
It can be seen that the operating system provides application programs with indirect access to physical devices using a method that involves the execution of three processes per physical device. The response time required by application programs 41, 42 to respond to random events equals the sum of the scheduling delays and execution times of the three operating system processes which cooperate in order to intercept and respond to interrupts originating from physical devices 1, 2, 3. Similarly, the service time required by application programs 41, 42 to access physical devices 1, 2, 3 equals the sum of the scheduling delays and execution times of the three operating system processes which cooperate in order to provide the requested service.
With reference to FIG. 1, application program 41 must execute prior to application program interface 31 in order to request services that require reading data and status words from physical device 1. Application program interface 31 must execute prior to the kernel 20 in order to generate the corresponding sequence of abstract device operations. The kernel 20 must execute prior to the device driver 11 in order to validate the sequence of abstract device operations and identify device driver 11 from among the device drivers that are present. The device driver 11 must execute prior to the kernel 20 in order to translate the abstract device operations into actual device operations in order to read the data and status words from physical device 1. Once this output becomes available, the device driver 11 creates a message containing the data and status words for input to the kernel. The kernel 20 must execute prior to application program interface 31 in order to receive the message containing the data and status words from the device driver 11. Finally, the application program interface 31 must execute prior to application program 41 in order to receive the message containing the data and status words from the kernel 20. In this example, process input-output relationships and process execution times are represented by the precedence graph of FIG. 2A. The numbers shown in parenthesis and brackets, all of which are quantities greater than zero, equal process execution times and scheduling delays, respectively. If process 41 begins execution at time t=0 then the aforementioned process sequence evolves as follows:
(a) process 41 for the period beginning at t=0 and ending at t=a.sub.R ;
(b) process 31 for the period beginning at t=a.sub.R +u.sub.R and ending at t=a.sub.R +b.sub.R +u.sub.R ;
(c) process 20 for the period beginning at t=a.sub.R +b.sub.R +u.sub.R +v.sub.R and ending at t=a.sub.R +b.sub.R +c.sub.R +u.sub.R +v.sub.R ;
(d) process 11 for the period beginning at t=a.sub.R +b.sub.R +c.sub.R +u.sub.R +v.sub.R +w.sub.R and ending at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +u.sub.R +v.sub.R +w.sub.R ;
(e) process 20 for the period beginning at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +u.sub.R +v.sub.R +w.sub.R +x.sub.R and ending at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +e.sub.R +u.sub.R +v.sub.R +w.sub.R x.sub.R ;
(f) process 31 for the period beginning at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +e.sub.R +u.sub.R +v.sub.R +w.sub.R +x.sub.R +y.sub.R and ending at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +e.sub.R +f.sub.R +u.sub.R +v.sub.R +w.sub.R +x.sub.R +y.sub.R ; and
(g) process 41 for the period beginning at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +e.sub.R +f.sub.R +u.sub.R +v.sub.R +w.sub.R +x.sub.R +y.sub.R and ending at t=a.sub.R +b.sub.R +c.sub.R +d.sub.R +e.sub.R +f.sub.R +g.sub.R +u.sub.R +v.sub.R +w.sub.R +x.sub.R +y.sub.R +z.sub.R.
It can be seen from this example that minimization of the service time required for application programs to read data and status words from physical devices, which corresponds to zero scheduling delay such that u.sub.R +v.sub.R +w.sub.R +x.sub.R +y.sub.R +z.sub.R =0, is not achieved in the prior art.
In another example, application program 41 must execute prior to application program interface 31 in order to request services that require writing data and control words to physical device 1. Application program interface 31 must execute prior to the kernel 20 in order to generate the corresponding sequence of abstract device operations. The kernel 20 must execute prior to the device driver 11 in order to validate the sequence of abstract device operations and identify device driver 11 from among the device drivers that are present. Finally, the device driver 11 must execute prior to the kernel 20 in order to translate the abstract device operations into actual device operations in order to write data and control words to physical device 1. In this example, process input-output relationships and process execution times are represented by the precedence graph of FIG. 2B. If process 41 begins execution at time t=0 then the process sequence evolves as follows:
(a) process 41 for the period beginning at t=0 and ending at t=a.sub.w ;
(b) process 31 for the period beginning at t=a.sub.w +u.sub.w and ending at t=a.sub.w +b.sub.w +u.sub.w ;
(c) process 20 for the period beginning at t=a.sub.w +b.sub.w +u.sub.w +v.sub.w and ending at t=a.sub.w +b.sub.w +c.sub.w +u.sub.w +v.sub.w ; and
(d) process 11 for the period beginning at t=a.sub.w +b.sub.w +c.sub.w +u.sub.w +v.sub.w +w.sub.w and ending at t=a.sub.w +b.sub.w +c.sub.w +d.sub.w +u.sub.w +v.sub.w +w.sub.w.
It can be seen from this example that minimization of the service time required for application programs to write data and control words to physical devices, which corresponds to zero scheduling delay such that u.sub.w +v.sub.w +w.sub.w +x.sub.w +y.sub.w +z.sub.w =0, is not achieved in the prior art.
Two types of prior information are available to schedule the activity of concurrent processes. The first type of prior information includes the priority of the task performed by each process. The second type of prior information includes process duration, execution time, and precedence constraints. A problem exists in that the kernel exploits the first type of prior information but not the second. The kernel 20 utilizes a simple priority queue or priority queue with preemption to schedule the activity of concurrent processes based task priority. The result is that the actual order and duration of process activation is inconsistent with process sequence input-output relationships and execution times. This inconsistency tends to increase scheduling delay, thereby degrading application program performance in terms of service and response times. Application program performance analysis, which takes the form of a queuing system with probabilistic arrival and service times, is non-deterministic and may only be characterized in terms of temporally averaged quantities.
In the prior art, a problem exists in that dynamic scheduling results in an exponential degradation in application program performance with increasing utilization of system resources. This behavior is predicted by queuing theory. Utilization of a system resource is characterized by a utilization factor. The utilization factor is a number between zero and one equal to the fraction of time that the resource is utilized by any process. The kernel is a process and must therefore allocation system resources to itself at the expense of the amount of resources which are available to all other processes which are present. A similar problem exists in that attempts to reduce scheduling delays using improved methods of dynamic scheduling must be traded against the fact that these methods require increased computation, thereby increasing scheduling delays due to increased kernel utilization of system resources.
In the prior art, a problem exists in that operating system performance cannot be traded against functionality in order to satisfy the broad spectrum of requirements corresponding to a diverse suite of applications. Operating systems developed for the IBM personal computer and compatibles, for example, have evolved to provide the functionality required by word processors, spreadsheets, and Web browsers. This functionality is not important in the case of real-time and embedded systems and engineering workstations. Furthermore, the resources which are consumed in order to provide this functionality tends to increase random scheduling delays. Engineering workstations require high-speed execution of computational algorithms used for modeling, simulation, filtering, prediction, and computer-aided design. Real-time and embedded systems monitor and control physical processes, and require data acquisition and processing capability in real-time, i.e., without the loss of temporal information, combined with a deterministic response to external events. Applications of real-time and embedded systems include smart appliances, environmental control, industrial process control, condition monitoring, signal and image processing, patient monitoring, data acquisition, robotics, machine vision, target tracking, security access, mobile robots, factory robots, sentry robots, traffic information display and control, components management, process control, quality control, vehicle control, telecommunication switches, and real-time event logging.
A problem exists in that new features are added to subsequent releases of the operating system, even after the benefit of the added features becomes negligible, the intellectual complexity of the application program interface becomes unmanageable, and average scheduling delays grow exponentially due to increased utilization of system resources. This problem is known in the prior art as creeping featuritis. An example of unbounded queuing delays resulting from creeping featuritis is the vicious virtual memory cycle, as described in the text book by G. Wm. Kadnier, entitled Windows NT 4: The Complete Reference, published by Osborne McGraw-Hill, and in particular Chapter 3 entitled "Setting Up Your System". Additional articles documenting creeping featuritis include articles by M. Leon, entitled "Java Battles Bloatware", which appeared on page 2 in InfoWorld, Jan. 6, 1997; M. Vizard, entitled "Is A Modular OS The Next Bloatware Cure?", which appeared on pages 1 and 18 in InfoWorld, Jan. 6, 1997; J. Dvorak, entitled "Inside Track", which appeared on page 89 in PC Magazine, Feb. 18, 1997; J. Dodge, entitled "Of Hard Drivers, Bloatware And Stubborn Fish Odor", which appeared on page 89 in PC Week, Jan. 27, 1997; J. Dodge, entitled "When It Comes To Their Own PCs, Pros Take It Personally", which appeared on page 3 in PC Week, Feb. 10, 1997; and B. Livingston, entitled "Though You'd Had Enough Fun? Here's More With Resource Ids In Windows 95", Infoworld, which appeared on page 32 in Jan. 27, 1997.
A problem exists in the prior art in that the testing used to validate the correct operation of operating system is inadequate. Recent experience indicates that the only difference between operating system development and maintenance is that a delivery date exists between these two activities. Evidence of the lack of validation testing is well documented in the current literature. See the articles by N. Petrely, entitled "IBM wins 1996 Fatal Error Awards And Shares General Protection Fault Awards With Microsoft", which appeared on page 126 in Infoworld Jan. 27, 1997; and B. Livingston, entitled "Though You'd Had Enough Fun? Here's More With Resource Ids In Windows 95", which appeared on page 32 of Infoworld in Jan. 27, 1997. Additional articles documenting the lack of verification testing include "The Bug Report: Microsoft To Fix Its Fixes", which appeared on page 14 in Infoworld, Jan. 20, 1997; and "The Bug Report: Service Pack 2 for Windows NT 4.0 Has Many Bug Fixes", which appeared on page 35 in Infoworld, Jan. 27, 1997.
In the case of a specific prior art operating system, which is the product of a corporation that also develops and markets application programs, certain routines of the application program interface are left undocumented. The purpose is to implement corporate strategy for gaining an unfair advantage in the development of competing products, which are not able to exploit the functionality of undocumented routines. Developers of competing products may be able to produce the functional equivalent to undocumented routines. Even so, the performance of the functional equivalent routines will always be degraded relative to that of the undocumented routines. This is because system resources are allocated to undocumented portions of the application program whether or not they are actually utilized by the application programs. The highest number of undocumented routines in the prior art is two hundred and fifty. For further information, the reader is referred to the text book by A. Scheilman, D. Maxey, and M. Pietrek, entitled Undocumented Windows: A Programmer's Guide to Reserved Windows API Functions, published by Addison-Wesley.
A problem exists in the prior art in that eleven incompatible versions of an operating system for the IBM PC/AT and compatibles have been released over a ten year period with additional releases scheduled in the near future. The effect of this shotgun approach to releasing operating systems is to allow a single corporation to control the environment in which development takes place. Beta program privileges for future releases of the operating system, which in some cases require steep license fees, has created a country club atmosphere in which members are given exclusive access to operating system specifications prior to its release. Early access provides a time-to-market lead in which to initiate product development and marketing programs. Non-members are sometimes able to regain competitive status by upgrading their product line, only to find their efforts invalidated in approximately one year with the release of a subsequent, incompatible version of the aforementioned operating system.
Prior art operating systems are limited in that, the functionality of the said operating system partially determines the functionality of application programs. One such operating system is DOS, which is distributed by IBM and Microsoft Corporation using the brand name PC-DOS and MS-DOS, respectively. It has been is widely acknowledged in the prior art that DOS is insufficient for modem computer applications. Section 1.2 of the web site at http://www.cmkrnl.com/faq.html confirms this insufficiency as follows: "In primitive PC operating environment such as DOS, drivers were specific to individual applications. For example, WordPerfect got pretty successful by including drivers that supported a wide variety of printers. But none of those drivers would work with any other printers." Another limitation of the DOS operating system is that concurrent processes are unable to access the video graphics adapter through a common graphics device interface. Despite the speed and efficiency of this operating system, this particular limitation contributed to the decreased popularity of application programs written for DOS as visual programs gained wider acceptance. Visual programs produce high-resolution, color graphics displays in the form of lines, polygons, solid shapes, symbols, text, and images. For further background, see the text book by Peter Norton entitled Programmer's Guide To IBM Personal Computers, published by Microsoft Press in 1985, and in particular Chapter 14 entitled "DOS Basics". A case study which documents the importance of graphical programs is given in the article by Dennis J. Velazquez, entitled "Making The Switch From DOS To Windows MMI", which appeared on pages 58 and 59 of the A-B Journal, November 1995.
Finally, a problem exists in the prior art in that applications are restricted to interface with the operating system which do provide a graphics device interface at very high levels of abstraction in an object-oriented environment. The utility of object-oriented programming is not universal. Programs for e-mail, word processing, web browsing, spreadsheets, and computer-aided drawing are assembled much in the same way an automobile is assembled from pre-defined components. For a many applications, however, software development in an object-oriented environment is similar to writing a story given a collection of stock paragraphs. Either the story is so similar to existing stories that it is not worth writing, or it is highly unlikely that the appropriate combination of paragraphs exist to write the story. In the later case, the time required to find an appropriate combination of stock paragraphs would be prohibitively long. Applications development demands the flexibility of a programming language just as writing a good book demands the flexibility of the English language.